#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

bool isInterleave(char* s1, char* s2, char* s3);

int main()
{
	char *s1 = "dbbca", *s2 = "aabcc", *s3 = "aadbbcbcac";
	printf("%d", isInterleave(s1, s2, s3));
	return 0;
}

bool isInterleave(char* s1, char* s2, char* s3)
{
	int lenS1 = strlen(s1), lenS2 = strlen(s2), lenS3 = strlen(s3);
	if (lenS1 + lenS2 != lenS3)
		return false;

	bool dp[lenS1 + 1][lenS2 + 1];
	memset(dp, 0, (lenS1 + 1) * (lenS2 + 1) * sizeof(bool));
	**dp = true;

	for (int i2 = 0; i2 < lenS2; i2++)
		if (s2[i2] == s3[i2])
			dp[0][i2 + 1] = true;
		else
			break;

	for (int i1 = 0; i1 < lenS1; i1++) {
		if (s1[i1] == s3[i1])
			dp[i1 + 1][0] = dp[i1][0];

		for (int i2 = 0; i2 < lenS2; i2++) {
			int i3 = i1 + i2 + 1;
			if (s3[i3] == s2[i2])
				dp[i1 + 1][i2 + 1] = dp[i1 + 1][i2];
			if (dp[i1 + 1][i2 + 1] != true && s3[i3] == s1[i1])
				dp[i1 + 1][i2 + 1] = dp[i1][i2 + 1];
		}
	}

	return dp[lenS1][lenS2];
}
